package reconstructItinerary;


import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;



public class Solution {
	int all;
	boolean flag=false;
	List<String> ans=new ArrayList<String>();
    HashMap<String, ArrayList<String>> graph = new HashMap<String, ArrayList<String>>();
    ArrayList<String> al = null;
    public List<String> findItinerary(String[][] tickets) {
    	all=tickets.length;

        List<String> temp=new ArrayList<String>();
        for (String[] ticket : tickets) {
            al = graph.get(ticket[0]);
            if (al == null) {
                al = new ArrayList<String>();
                graph.put(ticket[0], al);
            }
            al.add(ticket[1]);
        }
        for (ArrayList<String> curr : graph.values()) {
            Collections.sort(curr);
        }
        String from="JFK";
        temp.add(from);
        solve(from,graph,temp);
        return ans;
    }

	private void solve(String from, HashMap<String, ArrayList<String>> map,List<String> temp) {
		if (temp.size()==all+1) {
			if (ans.size()==0) {
				ans.addAll(temp);
				flag=true;
				return;
			}
			else{
				for (int i=0;i<ans.size();i++){
					String tempS,ansS;
					tempS=temp.get(i);
					ansS=ans.get(i);
					if (tempS.compareTo(ansS)<0){
						ans.clear();
						ans.addAll(temp);
						return;
					}
				}
			}
		}
		/*
        	int index=hash(from);
        	while ((from.equals(map[index][0])==false)&&(map[index][0]!=null)) index++;
        	while (from.equals(map[index][0])){
               if (bo[index]==false){
        			bo[index]=true;
        			temp.add(map[index][1]);
        			solve(map[index][1], map, temp);
        			bo[index]=false;
        			temp.remove(temp.size()-1);
        		}
               index++;
        	}
        */
		ArrayList<String> al =map.get(from);
        if (al==null) return;
        for (int i = 0; i < al.size(); i++){
        	String to=al.get(i);
        	temp.add(to);
        	al.remove(to);
        	solve(to, map, temp);
        	if (flag) return;
        	temp.remove(temp.size()-1);
        	al.add(i,to);
        	
        }
				
			
		
		
	}

	private int hash(String from) {
		int num1,num2,num3;
		num1=from.charAt(0)-'A'+1;
		num2=from.charAt(1)-'A'+1;
		num3=from.charAt(2)-'A'+1;
		return (num1*10000+num2*100+num3);
	}
	public static void main(String args[]){
		Solution so=new Solution();
		String[][] nums={{"JFK","KUL"},{"JFK","NRT"},{"NRT","JFK"}};		
		System.out.println(so.findItinerary(nums));
		}
}
/*
 * 题目大体：给n个[from,to]的机票，将其串联成行程
 * 核心：哈希+排序
 * 哈希字符串后根据字典序排序（排序保证第一次搜索便能得出正解）
 * key：学习java自带hashmap与排序用法
 */
